#include <iostream>
using namespace std;

void print_array(int a[],int n){
	for(int i = 0;i < n;i++){
		cout << a[i] << " ";
	}
	cout <<endl;
}

void shell_sort(int arr[],int n){
	int i,j,inc,key;
	// 初始增量2/n，每趟之后除以2
	for(inc = n/2;inc>0;inc/=2){
		// 每一趟采用插入排序
		for(i = inc;i < n;i++){
			key = arr[i];
			for(j = i;j >= inc && arr[j-inc] > key;j -= inc){
				arr[j] = arr[j-inc];
			}
			arr[j] = key;
		}
		print_array(arr,n);
	}
}

void test(int arr[],int n){
	for(int inc = n / 2;inc > 0;inc /= 2){
		for(int i = inc;i < n;i++){
			int key = arr[i];
			int j = i - inc;
			while(j >=0 && arr[j] > key){
				arr[j + inc] = arr[j];
				j-=inc;
			}
			arr[j+inc] = key;
		}
	}
}
int main(){
	int arr[] = {15,5,2,7,12,6,1,4,3,9,8,10};
	print_array(arr,12);
//	shell_sort(arr,12);
	test(arr,12);
	print_array(arr,12);
	return 0;
}
